package Q204;

/**
 * 计算质数
 * 统计所有小于非负整数 n 的质数的数量。
 *
 * @author 23737
 * @time 2021.11.19
 */
public class Test {
    public static void main(String[] args) {
        System.out.println(new Solution().countPrimes(10));
    }
}

/**
 * 暴力解题
 * 不过既然这是中等题，肯定有难度。大于50000就要超时。
 */
class Solution {
    public int countPrimes(int n) {
        if (n < 2) {
            return 0;
        }
        int count = 0;
        for (int i = 2; i < n; i++) {
            count += checkPrimeNumber(i) ? 1 : 0;
        }
        return count;
    }

    /**
     * 判断是否是质数
     * @param n
     */
    private boolean checkPrimeNumber(int n) {
        for (int i = 2; i <= Math.sqrt(n); ++i) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

class Solution2{
    public int CountPrimes(int n)
    {
        int count = 0;
        for (int i = 2; i < n; i++)
        {
            boolean sign = true;
            for (int j = 2; j < i; j++)
            {
                if (i % j == 0)
                {
                    sign = false;
                    break;
                }
            }
            if (sign)
                count++; ;
        }
        return count;
    }
}
